Network Algorithmics by George Varghese

Author:George Varghese [Varghese, George]
Language: eng
Format: epub
ISBN: 978-0-08-047964-4
Publisher: Elsevier Science
Published: 2005-11-15T00:00:00+00:00

10.3.2 Using Hardware Parallelism

Techniques based on perfect hashing do not completely provide worst-case guarantees. While they do provide worst-case search times of three to four memory accesses, they cannot guarantee worst-case update times. It is conceivable that an update takes an unpredictably long time while the software searches for a hash function with the specified bound on the number of collisions.

One can argue that exactly the same guarantees are provided every moment by millions of Ethernets around the world and that nondeterministic update times are far preferable to nondeterministic search times. However, proving that long update times are rare in practice requires either considerable experimentation or good analysis. This makes some designers uncomfortable. It leads to a preference for search schemes that have bounded worst-case search and update times.

An alternate approach is to apply hardware parallelism (P5) to a deterministic scheme such as binary search. Binary search has deterministic search and update times; its only problem is that search takes a logarithmic number of memory accesses, which is too slow. We can get around this difficulty by pipelining binary search to increase lookup throughput (number of lookups per second) without improving lookup latency. This is illustrated in Figure 10.5.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.